CAP 定理

分散型ウェブサービスを設計する際に一般的に望まれる 3 つの特性として、一貫性 (consistency)、可用性 (availability)、およびパーティション耐性 (partition tolerance) が擧げられる。しかし、これらの 3 つの特性をすべて同時に實現することは不可能である。本論文では、非同期ネットワークモデルにおいてこの命題を證明した上で、部分的に同期化されたモデルにおけるこのジレンマに對する解決策について考察する。

In this note, we have shown that it is impossible to reliably provide atomic, consistent data when there are partitions in the network. It is feasible, however, to achieve any two of the three properties: consistency, availability, and partition tolerance. In an asynchronous model, when no clocks are available, the impossibility result is fairly strong: it is impossible to provide consistent data, even allowing stale data to be returned when messages are lost. However in partially synchronous models it is possible to achieve a practical compromise between consistency and availability. In particular, most real-world systems today are forced to settle with returning “most of the data, most of the time.” Formalizing this idea and studying algorithms for achieving it is an interesting subject for future theoretical research.

一貫性 (consistency)

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. One important property of an atomic read/write shared memory is that any read operation that begins after a write operation completes must return that value, or the result of a later write operation.

この一貫性保証の下で、すべての操作に対して単一の全順序が存在しなければならない。つまり、各操作はあたかも単一の瞬間に完了したかのように見えなければならない。これは、分散共有メモリに対する要求が、単一ノード上で実行されているかのように振る舞い、操作を1つずつ処理することを要求することと等価である。原子的な読み書き共有メモリの重要な特性の一つは、書き込み操作が完了した後に開始された任意の読み出し操作は、その値を返すか、あるいはその後に行われた書き込み操作の結果を返さなければならないという点である。

可用性 (availability)

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. That is, any algorithm used by the service must eventually terminate. In some ways this is a weak definition of availability: it puts no bound on how long the algorithm may run before terminating, and therefore allows unbounded computation. On the other hand, when qualified by the need for partition tolerance, this can be seen as a strong definition of availability: even when severe network failures occur, every request must terminate.

分散システムが継続的に利用可能であるためには、システム内の非障害ノードが受信するすべての要求に対して必ず応答を返す必要がある。つまり、そのサービスで用いられるアルゴリズムは最終的に必ず終了しなければならない。ある意味では、この定義は可用性についての緩やかな要件と言える。なぜなら、アルゴリズムが終了するまでの実行時間に制限を設けていないため、無制限の計算を許容することになるからだ。一方で、パーティション耐性の要件を付加した場合、この定義は可用性についての厳格な要件と見なせる。たとえ深刻なネットワーク障害が発生したとしても、すべての要求は必ず終了しなければならないという条件が課されるからである。

分斷耐性 (partition-tolerance)

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost.)

分割耐性をモデル化するため、ネットワークでは任意の数のメッセージが1つのノードから別のノードへ送信された際に失われることが許容される。ネットワークが分割状態にある場合、分割の一方のコンポーネントに属するノードから他方のコンポーネントに属するノードへ送信されたすべてのメッセージは失われる。（また、任意のメッセージ損失パターンは、メッセージが失われたその瞬間に通信中のノードを一時的に分離する分割状態としてモデル化可能である）

Theorem 1

It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

Availability

Atomic consistency

in all fair executions (including those in which messages are lost).

非同期ネットワークモデルにおいて、以下の特性をすべての公平な実行環境（メッセージ損失が発生する場合を含む）で保証する読取り/書込みデータオブジェクトを実装することは不可能である：

可用性

原子的一貫性

これらの特性を同時に満たすことは不可能である。

Corollary 1.1

It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

Availability, in all fair executions,

Atomic consistency, in fair executions in which no messages are lost.

非同期ネットワークモデルにおいて、以下の特性を保証する読み書きデータオブジェクトを実装することは不可能である：

すべての公平な実行環境における「可用性」、および

メッセージが消失しない公平な実行環境における「原子的一貫性」

Theorem 2

It is impossible in the partially synchronous network model to implement a read/write data object that guarantees the following properties:

Availability

Atomic consistency

in all executions (even those in which messages are lost).

部分的同期ネットワークモデルにおいて、以下の特性をすべての実行環境で保証する読取り/書込みデータオブジェクトを実装することは不可能である：

可用性

原子的一貫性

（メッセージが失われた場合を含む、あらゆる実行ケースにおいて）

Definition 3

A timed execution, α, of a read-write object is Delayed-t Consistent if:

1. P is a partial order that orders all write operations, and orders all read operations with respect to the write operations.

2. The value returned by every read operation is exactly the one written by the previous write operation in P (or the initial value, if there is no such previous write in P).

3. The order in P is consistent with the order of read and write requests submitted at each node.

4. (Atomicity) If all messages in the execution are delivered, and an operation θ completes before an operation φ begins, then φ does not precede θ in the partial order P,

5. (Weakly Consistent) Assume there exists an interval of time longer than t in which no messages are lost. Further, assume an operation, θ, completes before the interval begins, and another operation, φ, begins after the interval ends. Then φ does not precede θ in the partial order P.

読み取り/書き込みオブジェクトに対する時間制限付き実行 α が Delayed-t 一貫性を満たす条件は以下の通りである：

1. P は全ての書き込み操作を順序付ける部分順序関係であり、全ての読み取り操作をそれらの書き込み操作に対して順序付けるものでなければならない。

2. 各読み取り操作が返す値は、P において直前に行われた書き込み操作によって実際に書き込まれた値と完全に一致している必要がある（そのような直前の書き込み操作が存在しない場合は、初期値でなければならない）。

3. P における順序関係は、各ノードから送信された読み取り/書き込み要求の順序関係と整合性が保たれていなければならない。

4. (原子性) 実行中の全てのメッセージが確実に配信され、ある操作 θ が別の操作 φ の開始前に完了した場合、P の部分順序において φ は θ よりも先行してはならない。

5. (弱一貫性) メッセージが消失しない時間間隔が t よりも長い区間が存在すると假定する。さらに、ある操作 θ がこの区間の開始前に完了し、別の操作 φ がこの区間の開始後に開始した場合、P の部分順序において φ は θ よりも先行してはならない。

Theorem 4

The modified centralized algorithm is Delayed-t consistent.

修正された集中型アルゴリズムは遅延t一貫性を満たす。

コンセンサスの問題にはプロセスの非同期システムが含まれてをり、そのいくつかは信賴性が缺落してゐることがある。課題は、信賴できるプロセスが 2 値の下で合意することである。本論文では、この課題に對するどのやうなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示してゐる。對照的に、同期のケースでは "Byzantine Generals" 問題として解決が知られてゐる。

FLP 論文

BASE & ACID

ACID

原子性 (atomicity)

一貫性 (consistemcy)

獨立性 (isolation)

永續性 (durability)

BASE

basically available

soft-state

結果整合性 (eventually consistent)

部分的同期 (partial synchrony)

分散システムにおける部分的同期の槪念が導入される。部分的同期は、同期システムと非同期システムの中閒的な狀態を指す。同期システムでは、あるプロセッサから別のプロセッサへメッセージを送信するのに必要な時閒に既知の固定上限Δが存在し、異なるプロセッサ閒の相對速度にも既知の固定上限Φが定義されてゐる。一方、非同期システムではこのやうな固定上限ΔとΦは存在しない。部分的同期の一つの形態では、固定上限ΔとΦは存在するものの、事前には未知である。この場合の課題は、上限値ΔとΦの實際の値にかかはらず、部分的同期システムにおいて正しく動作するプロトコルを設計することである。別の形態の部分的同期では、上限値は既知であるものの、それらが保證されるのは未知の時點T以降に限られる。この場合、プロトコルは時閒Tがいつ發生しようとも正しく動作するやうに設計されなければならない。本硏究では、樣々な種類の部分的同期狀態と各種障害モデルに對して、耐障礙性合意プロトコルを提案する。さらに、ほとんどの場合において本プロトコルが許容可能な障礙數に關して最適であることを示す下限値も提示する。部分的同期プロセッサ向けの合意プロトコルでは、新たに開發した耐障礙性「分散クロック」プロトコルを採用してゐる。このプロトコルにより、部分的同期狀態にあるプロセッサは、ある程度の共通的な時閒槪念に到達することが可能となる。

SALT

decentralized databases での一貫性 model

本論文では、分散データベースシステム「Salt」を提案する。Salt は、開發者が漸進的に BASE アプローチを採用することで、ACID 準據アプリケーションの性能とスケーラビリティを向上させることを可能にするシステムである。Salt の開發動機は、パレートの法則に基づいている。多くのアプリケーションにおいて、實際に ACID の性能限界を試すトランザクションはごく少數に過ぎない。この知見を活用するため、Salt では「BASE トランザクション」といふ新たな抽象槪念を導入した。BASE トランザクションは、原子性や耐久性といった望ましい特性を保持しつつ、Salt の新規機構である「Isolation (分離)」メカニズムによって、他のトランザクションに對して提供する分離レベルの粒度を、自身が BASE トランザクションであるか ACID トランザクションであるかに應じて制禦できる。このやうな柔軟性により、BASE トランザクションは BASE パラダイムの性能上の利點を享受できる一方で、殘りの ACID トランザクションが享受する保證を損なうことはない。例えば、オープンソースのチケット管理システム Fusion Ticket において、Salt を MySQL Cluster ベースで實裝した場合、11 個のトランザクションのうち 1 つを BASE 化するだけで、ACID 實裝時と比較してスループットが 6.5 倍向上することが確認されてゐる。

transactional context

逐次的 (sequential)

Transactions occur in some sequential ordering… though that may be determined by the winning miner in some blockchains.

合意された (agreed)

There is a consensus on what is to transpire to produce a common state… which may require a leader election or a winner such as in Proof of Work systems.

導かれた (ledgered)

All evidence of transactions are maintained in a historical ledger of events… which allows the current state to be verified as correct.

改竄されない (tamper-resistant)

A significant plurality is required to alter committed transactions… often called immutability but that’s a misnomer.

systemic context

對稱的 (symmetric)

Every node is empowered to validate their data (I modified this a bit from their paper because they assume public consensus networks but this can be abstracted to private chains that do not have symmetric responsibility of nodes).

管理者なし (admin-free)

I prefer the term ‘autonomous’, but it means there’s a self-governance to the system and no one node can change the system on its own.

導かれた (ledgered)

All peers maintain a ledgered system of the data and have rules for negotiating the addition of blocks onto the ledger.

時閒的に合意された (time-consensual)

There is a defined expectation of approximate block creation times.

network 上の name service は以下の三つの性質を全ては滿たせない

human-meaningful

Meaningful and memorable (low-entropy) names are provided to the users.

secure

The amount of damage a malicious entity can inflict on the system should be as low as possible.

悪意ある主体がシステムに及ぼし得る損害の規模は、可能な限り最小限に抑えるべきである。

decentralized

Names correctly resolve to their respective entities without the use of a central authority or service.

中央管理機関やサービスを使用せずに、各名称がそれぞれの実体に正しく解決される。